package selected;

import java.util.*;

public class J0820 {
    // 1. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        // 使用hash表来维护窗口
        int left = 0, right = 0, len = s.length(), ret = 0;
        int[] hash = new int[128];
        while(right < len){
            char in = s.charAt(right);
            hash[in]++;
            while(hash[in] > 1){
                char out = s.charAt(left++);
                hash[out]--;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
    // 2. 找到字符串中所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        for(char c : pp){
            hash2[c - 'a']++;
        }
        int left = 0, right = 0, count = 0, len = s.length();
        List<Integer> ret = new ArrayList<>();
        while(right < len){
            char in = ss[right];
            if(++hash1[in - 'a'] <= hash2[in - 'a']) count++;
            while(right - left + 1 > p.length()){
                char out = ss[left++];
                if(hash1[out - 'a']-- <= hash2[out - 'a']) count--;
            }
            if(count == p.length()) ret.add(left);
            right++;
        }
        return ret;
    }
    // 3 计算前缀和
    public void countDpSum(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); int q = in.nextInt();
        int[] nums = new int[n + 1];
        for(int i = 1; i <= n; i++){
            nums[i] =in.nextInt();
        }

        // 构造出前缀和数组
        long[] dp = new long[n + 1];
        // 下标从1开始，避免溢出
        for(int i = 1; i <= n; i++){
            dp[i] = nums[i] + dp[i - 1];
        }

        while(q > 0){
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
            q--;
        }
    }
    // 4. 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        // 去i前面的数的前缀和集合中，找有多少个前缀和为 sum[i] - k 的数
        int ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int sum = 0; // 创建一个记录变量，记录 i - 1位置的前缀和
        for(int num : nums){
            sum += num;
            ret += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
}
